1. Field of the Invention
This invention relates to software verification. More particularly, this invention relates to test program generation for validating the implementation of a specification of a software program that is capable of executing multiple independent operations.
2. Description of the Related Art
Concurrent and parallel software supports operations involving interdependent interactions between its classes and objects. Such operations may occur concurrently or in parallel. Concurrent operations occur in the same address space, but run in separate threads. Parallel operations occur in separate address spaces. Since the operations occur in separate address spaces, their associated objects may be distributed across multiple hosts.
An important aspect of designing an advanced computer software system is the ability to thoroughly test its implementation in order to assure that the implementation complies with desired specifications. Usually, such verification requires the generation of test programs to verify that the system behaves properly under a wide variety of circumstances.
Traditional software testing involves study of the software system by the tester, who then writes and executes individual test scenarios that exercise the software being tested. Testing may require validation of many functional levels, which substantially increases the complexity of the task. In the past, test scenarios were manually generated, but now this task is sometimes automated, using computer implemented test program generators.
Test program generators are basically sophisticated software engines, which are used to create numerous test cases. By appropriate configuration, it is possible for test program generation either to be focused on very specific ranges of conditions, or to be broadened to cover a wide range 90 of logic. Today, large numbers of test cases can be created in the time that a single test case could be written manually.
During the past decade, model-based random test program generators have become popular in processor architectural design verification and software testing. Model-based test generation involves the generation of a suite of tests from an abstract model of an application's behavior. The model is derived from a specification of the application. In many model-based testing situations, the behavior models are described as finite state machines (FSM). Such FSM models describe the possible states of the application and the transitions from state to state caused by operations or stimuli. Test suites generated from these behavior models cover different operation invocation patterns according to the testing goals.
Typical of conventional approaches for generating test programs is U.S. Pat. No. 5,394,347 to Kita et al., which discloses a method of modeling a specification as an extended finite state machine, then performing a depth-first traversal of the resulting state diagram to generate a path file as a basis for a test program.
In U.S. Pat. No. 5,918,037 to Tremblay et al., it is proposed to employ a test generator that automatically produces test programs based on a finite state machine model of the software. Limiting the number of test programs is achieved by controlling loop execution, and by appropriately setting the coverage level for the model, known as “transition cover testing”. This approach seeks to specify that each transition within the finite state machine model be exercised once. The generator is capable of specifying different coverage levels for selected portions of the program under test, so that critical portions might be exhaustively tested, while other portions receive less comprehensive testing.
Test programs are repetitively executed by an execution engine, using suites of input data. The results of execution are compared in some way with design specification. Generic validation engines are known for this purpose. The validation engine need not have specific knowledge of the design, and can be used in the testing of many system components. Some validation engines maintain state tables for tracking outcomes, such as a sequence of events. Such an engine typically implements a predetermined algorithm for validating the outcome or sequence of events.
The standard TTCN (ISO/IEC-9646) is a notation standardized by the International Organization for Standardization (ISO) and the Telecommunication Standardization Sector of the International Telecommunications Union (ITU-T) for the specification of tests for communicating systems. The standard TTCN has been employed in many test generation and execution environments. A TTCN-based model-based tool for the generation of test suites suitable for complex systems, known as the Telelogic Tau TTCN Suite, is produced by Telelogic AB, PO Box 4128, Kungsgatan 6, SE-203 12 Malmy, Sweden. This is an example of a commercial test execution engine, the input of which is an abstract TTCN test suite. The standard TTCN provides concurrency and synchronization primitives. However, a tester interested in validating concurrent aspects of a system-under-test is required to write specialized test cases.
Another model-based generator is the GOTCHA-TCBeans Software Test Tool Kit, which has been developed by International Business Machines Corporation, New Orchard Road, Armonk, N.Y. 10504. This tool provides a framework designed to assist testers in developing, executing and organizing function tests directed against Application Program Interfaces (APIS) and software protocols written in Java™, C or C++.
The product LoadRunner®, available from Mercury Interactive, Inc. 1325 Borregas Avenue 220, Sunnyvale, Calif. 94089, USA, emulates multiple users, called virtual users. The virtual users execute Vuser scripts, written in a proprietary testing language. The tester creates a Vuser script, parameterizes the script, and then configures the LoadRunner software to start the virtual user execution. If the tester wants to synchronize activity between the different virtual users he must add synchronization points to the scripts, known as rendezvous.
Known test program generators are limited in their abilities to deal with systems having concurrent and parallel operations, for example multiprocessors and complex software suites such as client/server applications, database and transaction processing systems. The traditional approach to validating independent operations is either to model the independent behavior of the multiple operations or processes, or to run test cases in parallel.
Modeling independent behavior is not a good solution, because it results in excessively large and intractable models. One of the biggest drawbacks of finite state machine modeling is state explosion. Modeling independent events exacerbates this problem. Running test cases concurrently or in parallel is even less effective, because it results in a lack of control and clarity. There may be many concurrent operations in a test case, and the location of a fault trigger that is uncovered by this technique is often obscure. Lack of control over the concurrent operations further complicates interactive fault debugging.
In view of the above-noted drawbacks of conventional approaches, it would be desirable to improve the methods and techniques for the validation of concurrent and parallel systems.